import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Stream;

/**
 * 多数元素
 * 题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于n/2的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * <p>
 * 示例1:
 * 输入: [3,2,3]
 * 输出: 3
 * <p>
 * 示例2:
 * 输入: [2,2,1,1,1,2,2]
 * 输出: 2
 * <p>
 * 来源：力扣（LeetCode-169）
 * 链接：https://leetcode-cn.com/problems/majority-element
 *
 * @author godfrey
 * @since 2020-11-18
 */
@DisplayName("多数元素")
public class MajorityElement {

    static Stream<Arguments> testArguments() {
        return Stream.of(
                Arguments.arguments((Object) new int[]{3, 2, 3}),
                Arguments.arguments((Object) new int[]{2, 2, 1, 1, 1, 2, 2})
        );
    }

    @DisplayName("排序-时间复杂度O(nlogn)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void majorityElement(int[] nums) {
        Arrays.sort(nums);
        System.out.println(nums[nums.length / 2]);
    }

    @DisplayName("哈希-时间复杂度O(n)，空间复杂度O(n)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void majorityElement2(int[] nums) {
        if (nums.length <= 1) {
            System.out.println(nums[0]);
        }
        Map<Integer, Integer> map = new HashMap<>();
        int num = 0;
        for (int i : nums) {
            if (!map.containsKey(i)) {
                map.put(i, 1);
            } else {
                int j;
                if ((j = map.get(i) + 1) > nums.length / 2) {
                    num = i;
                    break;
                }
                map.remove(i);
                map.put(i, j);
            }
        }
        System.out.println(num);
    }

    @DisplayName("线性解法-时间复杂度O(n)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void majorityElement3(int[] nums) {
        int result = 0, count = 0;
        for (int x : nums) {
            if (count == 0) {
                result = x;
                count = 1;
            } else if (result == x) {
                ++count;
            } else {
                --count;
            }
        }
        System.out.println(result);
    }
}
